Sau khi đạt được một số tiếng tăm ở Rome như một luật gia và một nhà hùng biện,ông bắt đầu sự nghiệp quân sự.Chiến dịch tham gia đầu tiên là dưới quyền Quintus Servilius Caepio tại trận Arausio, nơi mà ông ta thể hiện sự can đảm phi thường.Phục vụ dưới quyền Gaius Marius năm 102 TCn,Sertorius đã thành công trong vai trò lính do thám về sự di chuyển của các bộ tộc German mà đã đánh bại Caepio. Sau thành công này, ông tham gia vào trận đánh lớn Trận Aquae Sextiae (nay là Aix-en-Provence, Pháp) mà người Teutones đã chịu thất bại quyết định.Năm 97 TCn,ông phục vụ ở Hispania (bán đảo Iberian bao gồm Tây Ban Nha và Bồ Đào Nha) như là lực lượng bảo vệ quan bảo dân dưới quyền Titus Didius.

Năm 91 TCn,ông đảm nhận chức quan coi quỹ ở Cisalpine Gaul, nơi ông phụ trách tuyển dụng và đào tạo lính lê dương cho cuộc chiến tranh đồng minh.Trong thời gian này, ông gặp phải một vết thương làm cho ông bị mất một mắt.Sau khi ông trở về Rome ông chạy đua tới chức quan bảo dân nhưng Lucius Cornelius Sulla cản trở nỗ lực của ông(chưa rõ nguyên nhân).Đây là lý do Sertorius chống lại ông ta.

Sau khi Sulla buộc Marius phải tha hương và Sulla rời Rome để chống lại Mithridates,bạo lực lại xảy ra giữa phe Optimates được lãnh đạo bởi chấp chính quan Gnaeus Octavius, và phe Populares,được lãnh đạo bởi chấp chính quan Lucius Cornelius Cinna. Sertorius tuyên bố theo Cinna và phe Populares. Mặc dù ông đã có một đánh giá không tốt bởi Marius,ông tán thành việc quay trở về của Marius vì hiểu rằng Marius trở về theo lời đề nghị của Cinna chứ không không phải là của riêng mình. Sau khi Octavius giao lại Rome cho các lực lượng của Marius, Cinna, và Sertorius vào năm 87TCN, Sertorius bỏ phiếu trắng trong việc trục xuất người đồng nghiệp đang chỉ huy quân đội của mình. Sertorius đã đi xa như vậy để khiển trách Marius.